package org.example;

public class Main {
    public static void main(String[] args) {
        final String str = "c++/go/cangjie/编程语言 - 文本搜索性能大比拼，谁才是字符串比较的性能王者？请看2024年度性能测试野榜排名——c++/go/cangjie/编程语言";
        //var str = "c++/go/ 测试文本 c++/go/"
        StringBuilder text = new StringBuilder(); //  使用 strings.Builder 构建超多文本，string 变量超过10万行文本以后拼接会非常卡
        int num = 1000000;            // 100万行文本

        for (int i = 0; i < num; i++) {
            // 文本后面 + 数字编号，保证每一行都是不同的
            if (i % 2 == 0) {
                //偶数行不追加换行符，保持前后有相同字符串，kmp算法匹配指定字符串时，就会跳过公共前缀，便于测试算法的性能，否则就跟普通的BF算法没有区别了
                text.append(str);
            } else {
                text.append("\n" + str).append(i).append("\n");
            }
        }

        // 设置最后一行为固定字符串，方便我们查找
        final String lastRowStr = str + (num + 1);
        text.append(lastRowStr);
        int pos = -1;

        // 由于100万文本中含有中文，无法直接按照索引获取字符比较，因此我们将原始字符串转为 []rune
        String textRune = text.toString();
        // ↑↑↑  以上构建待处理的字符串过程放置在本次文本比较时间之间之外 ，我们本次只是测试文本比较性能 ↑↑↑

        final long startTime = System.currentTimeMillis();
        // 循环测试 10 次
        int loopCount = 10;
        for (int i = 0; i < loopCount; i++) {
            pos = findStr(textRune, lastRowStr);
        }
        long useMs = System.currentTimeMillis() - startTime;
        System.out.println("100万行文本字符串查找目标字符串(KMP算法)，字符串位置：" + pos + " 单次耗时(ms): " + (useMs / 10));
    }

    // KMP 算法理解起来比较费劲，本篇需要数学理论支撑才能看懂代码
    // 这里展示的代码基本是将阮一峰这篇文章中的计算过程翻译为程序代码，文章地址：https://kb.cnblogs.com/page/176818/

    // @pattern 表示模式参数(待查找的字符串)
    static int[] getNext(String patternRune) {
        int length = patternRune.length();
        // next 数组默认全部填充 0
        int[] next = new int[length];

        int j = 0;
        String leftStr = "";
        String rightStr = "";

        // 第一个元素的匹配值默认已经是0，这里只需要从第2个元素（索引从1开始）计算相关的 next 匹配表
        for (int i = 1; i < length; i++) {
            j = 0;
            while (j < i) {
                // 优先匹配最长前缀和后缀
                leftStr = patternRune.substring(0, i - j); // 左侧字符串，表示可能的前缀
                rightStr = patternRune.substring(j + 1, i + 1);// 右侧字符串，表示可能的后缀
                if (leftStr.equals(rightStr)) {
                    next[i] = leftStr.length();
                    break;
                }
                j++;
            }
        }
        return next;
    }


    // @origin 原始字符串
    // @pattern 模式字符串(需要寻找的字符串)
    static int findStr(String originRune, String patternRune) {
        int[] next = getNext(patternRune);

        //  搜索模式字符在目标字符中的位置
        int i = 0;
        int j = 0;
        int hasCommonStrNum = 0; // 公共字符个数

        while (i < originRune.length()) {
            if (originRune.charAt(i) == patternRune.charAt(j)) {
                j++;
            } else if (j > 0) {
                hasCommonStrNum = next[j - 1];
                j = 0;
                // 这里和阮一峰文章计算偏移量有差异，文章是将模式字符串右移动，
                // 代码里面我们是将原始字符串左移，而模式字符串始终保持不动
                i = i - hasCommonStrNum;
                continue;
            } else {
                // j==0的情况就是第一个字符匹配失败了
                j = 0;
            }
            i++;

            if (j == patternRune.length()) {
                return i - patternRune.length();
            }
        }

        return -1;
    }
}